package com.example.demo.controller;


import com.sun.scenario.effect.Brightpass;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @descript 字节跳到算法题
 * @author sunny
 */
public class ByteDanceCodeTest {
    /**
     * 1.二叉树镜像 ****
     * 2.大概是题目给出了一个例子，然后让根据这个例子，在输入的数组中找出第k大的素数，输入数组可能包含不是素数的数字 ****
     * 8.一个顺序递增的数组，内含重复的数，现查找一个给定的数在不在数组，在的话给出最后一个出现的index ****
     * 9.  堆排序相关 ****
     * 10. 动态规划 ****
     * 两个单链表求和 *****
     *实现一个有顺序的LinkedList，实现deleteAll(int val)方法删除所有值为val的节点，和save(int val)方法添加一个值为val的节点。******
     * 输入一个int数组，返回一个数组，其中奇数都在左边，偶数都在右边  附加条件 不使用额外的空间 ***
     *
     *
     * 自己设计hash
     * 如何限制每分钟每个手机号短信发送数量
     * 算法题leetcode 670
     * 栈，增加一个max方法；
     * 找到一个文件里出现次数最多的的数字，文件大小远大于内存容量
     * 给一个数组和一个整数，输出数组中所有和为给定整数的元素下标。
     */


    /**
     * 两数之和 三数之和
     *
     */

    /**
     * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
     *
     * 示例 1 :
     *
     * 输入: 2736
     *    7632
     *           选出一个最大 看是不是在首位 是 ->在
     *
     * 输出: 7236
     * @param nums
     */
    public static int[] getMax(int nums[]){
        if(nums == null || nums.length==0){
            return null;
        }
        int max =0;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for(int j = 0;j<nums.length;j++){ //j= 0 -3;
            for(int i=j;i<nums.length;i++){ //0
                if(j==0){
                    hashMap.put(nums[i],i);
                }
                max = nums[i]>max?nums[i]:max;
            }
            if(max>nums[j]){
                swap(nums,j,hashMap.get(max));
                return nums;
            }
            max =0;
        }
       return nums;
    }



    public static void jiOu(int nums[]){
        if(nums==null || nums.length==0|| nums.length==1){
            return;
        }
        int temp = nums.length-1;
        for(int i=0;i<=temp;){
            if(isOu(nums[i])){
                swap(nums,i,temp);
                temp--;
            }else {
                i++;
            }
        }
    }

    /**
     *  1 2 3 4 5 6 7 8
     * @param nums
     */
    public static void jiou(int nums[]){
        if(nums==null || nums.length==0|| nums.length==1){
            return;
        }
        int left = 0;
        int right = nums.length-1;
        while(true){
            while(isOu(nums[right])&&left<right){
                right--;
            }
            while(!isOu(nums[left])&&left<right){
                left++;
            }
            swap(nums,left,right);
            if(left == right){
                break;
            }
        }
    }

    public static boolean isOu(int num){
        boolean result = false;
        if(num%2==0){
            result = true;
        }
        return result;
    }
    /**
     * 1 2 3 4 5 6  k  = 6 index = 1-6 = 0
     *  在输入的数组中找出第k大的数 1
     */
    public static int getLargeIndex(int [] nums ,int k){
        if(nums==null || nums.length==0 || nums.length-k<0){
            return  -1;
        }
        int start = 0;
        int end = nums.length-1;
        int middle = partition(nums,start,end);

        while(true){
            if(middle== nums.length-k){
                return nums [middle];
            }else  if (middle< nums.length-k){
               middle =  partition(nums,middle+1,end);
            }else {
                middle = partition(nums,start,middle-1);
            }
        }
    }


    /**
     *  4 5 6 7 8 1 2 3  - > 4 1 6 7 8 5 2 3
     * @param nums
     * @param start
     * @param end
     * @return
     */
    private static int partition(int[] nums, int start, int end) {
        int stardent = nums[start];
        int temp = start;
        for(int i = start+1;i<=end;i++){
            if(stardent>nums[i]){
                temp = temp +1;
                swap(nums,i,temp);
            }
        }
        swap(nums,start,temp);
        return temp;
    }
    public static void swap(int nums[],int start,int end){
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }


    static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value, TreeNode left, TreeNode right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int value) {
            this.value = value;
        }
    }

    /**
     * 二叉树镜像
     *       1                  1
     *    2     3     ->     3      2
     *   4 5   6  7        7  6   5  4
     * @return
     */
    public static TreeNode build(){
         TreeNode root7 = new  TreeNode(7);
         TreeNode root6 = new  TreeNode(6);
         TreeNode root5 = new  TreeNode(5);
         TreeNode root4 = new  TreeNode(4);
         TreeNode root3 = new  TreeNode(3,root6,root7);
         TreeNode root2 = new  TreeNode(2,root4,root5);
         TreeNode root = new  TreeNode(1,root2,root3);
        return root;
    }

    public static void printFront(TreeNode root){
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();

        while(!stack.isEmpty() || root!=null){
            if(root!=null){
                System.out.println(root.value);
                stack.push(root);
                root = root.left;
            }else {
                TreeNode pop = stack.pop();
                root = root.right;
            }
        }
    }

    public static int klarge(TreeNode root,int k){
        int res = -1;
        if(root ==null){
            return res;
        }
        dfs1(root,k,res);
        return res;
    }
    private static void dfs1(TreeNode root,int k,int res){
        if(root==null){
            return;
        }
        dfs1(root.left,k,res);
        if(k==0){
            return;
        }
        if(--k==0){
            res = root.value;
        }
        dfs1(root.right,k,res);
    }
    public static TreeNode mirror3(TreeNode root){
        if(root==null){
            return root;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        mirror3(root.left);
        mirror3(root.right);
        return root;
    }

    public static void main(String[] args) {
        TreeNode build = build();
        TreeNode mirror = mirror2(build);
        printTree(mirror);
    }

    public static void printTree(TreeNode root){
        if(root ==null){
            return;
        }

        LinkedList<TreeNode> aque = new LinkedList<>();
        aque.offer(root);
        while(!aque.isEmpty() ){
            TreeNode poll = aque.poll();
            System.out.println(poll.value);
            if(poll.left!=null){
                aque.offer(poll.left);
            }
            if(poll.right!=null){
                aque.offer(poll.right);
            }
        }
    }



    public static TreeNode mirror2(TreeNode root){
        if(root==null){
            return root;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        mirror2(root.left);
        mirror2(root.right);
        return root;
    }


    public static TreeNode mirror1(TreeNode root){
        if(root==null){
            return null;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode pop = queue.pop();
            TreeNode right = pop.right;
            pop.right = pop.left ;
            pop.left = right;
            if(pop.left !=null){
                queue.offer(pop.left);
            }
            if(pop.right!=null){
                queue.offer(pop.right);
            }
        }
        return root;
    }
    public static TreeNode mirror(TreeNode root){
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();

        stack.push(root);
        while(!stack.empty()){
            TreeNode pop = stack.pop();
            TreeNode right = pop.right;
            pop.right = pop.left ;
            pop.left = right;
            if(pop.left !=null){
                stack.push(pop.left);
            }
            if(pop.right!=null){
                stack.push(pop.right);
            }
        }
        return root;
    }

    public static void print(TreeNode root){
        if(root==null){
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            System.out.println(poll.value);
            if(poll.left!=null){
                queue.offer(poll.left);
            }
            if(poll.right!=null){
                queue.offer(poll.right);
            }
        }
    }




    /**
     * 查找右边界   1 2 2 2 3 4
     * @param nums
     * @param target
     * @return
     */
    public static int findleft(int nums[],int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length;
        while(start<end){
            int middle = start+((end-start)>>>1);
            if(nums[middle]==target){
                end = middle;
            }else if(nums[middle]<target){
                start = middle+1;
            }else {
                end = middle;
            }
        }
        if(start== nums.length){
            return -1;
        }else   {
            return start;
        }

    }
    /**
     * 查找右边界   1 2 2 2 3 4
     * @param nums
     * @param target
     * @return
     */
    public static int find(int nums[],int target){
        if(nums==null || nums.length==0){
            return -1;
        }
        int start = 0;
        int end = nums.length;
        while(start<end){
            int middle = start+((end-start)>>>1);
            if(nums[middle]==target){
                start = middle+1;
            }else if(nums[middle]<target){
                start = middle+1;
            }else {
                end = middle;
            }
        }
        if(start==0 ||nums[start-1]!=target){
            return start-1;
        }else   {
            return start-1;
        }

    }


}


